/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-06-10
 * Time: 22:57
 */
import java.util.*;

/**
 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
 输入描述：
 输入包括1行字符串，长度不超过100。
 输出描述：
 可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
 *
 *  */
//根节点
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}
public class CreateTree {
        //定义变量i ,从0开始,遍历str字符串
        public static int  i = 0;
        public static TreeNode create( String str) {
            TreeNode ret = null;
            //当不为'#',创建新节点
            if( str.charAt(i) != '#') {
                ret = new TreeNode( str.charAt(i));
                i++;
                //递归创建新节点的左边和右边
                ret.left = create( str );
                ret.right = create( str );
            } else {
                //当为'#'跳过'#'号
                i++;
            }
            return ret;
        }
        //中序遍历
        public static void inOrder( TreeNode root) {
            if( root == null) return ;
            inOrder(root.left);
            System.out.print( root.val + " ");
            inOrder(root.right);
        }

        public static void main( String[] args) {
            Scanner scanner = new Scanner( System.in);
            while( scanner.hasNextLine() ) {
                String str = scanner.nextLine();
                TreeNode root = create(str);
                inOrder(root);
            }
        }
}
